#include <bits/stdc++.h>
using namespace std;

// 定义全局变量
long long data_[11], n;    // data_数组存储输入的n个正整数，n为数的个数
int res = 10;               // res用于存储当前最小的分组数，初始设为最大可能值10
long long visited[11];     // visited数组用于记录每个组的状态（当前组内的数的乘积）

// 计算两个数的最大公约数
int gcd(long long a, long long b) {
    if(b == 0) return a;    // 如果b为0，最大公约数即为a
    return gcd(b, a % b);   // 递归调用，使用欧几里得算法
}

// 深度优先搜索 (DFS) 函数，用于尝试将第step个数分配到不同的组中
void dfs(int k, int step) {
    // 如果已经处理完所有数
    if (step > n) {
        res = min(res, k);  // 更新最小分组数
        return;
    }

    // 尝试将当前数分配到已有的k个组中
    for(int i = 1; i <= k; i++) {
        // 检查当前数与组i中的数是否互质
        if(gcd(visited[i], data_[step]) == 1) {
            visited[i] *= data_[step];    // 将当前数加入组i（更新组i的乘积）
            dfs(k, step + 1);             // 递归处理下一个数
            visited[i] /= data_[step];    // 回溯，移除当前数
        }

        // 尝试将当前数放入一个新的组k+1中
        visited[k + 1] *= data_[step];    // 将当前数加入新组k+1
        dfs(k + 1, step + 1);             // 递归处理下一个数，并增加一个新组
        visited[k + 1] /= data_[step];    // 回溯，移除当前数
    }
}

int main() {
    cin >> n;    // 读取数的个数

    // 读取n个正整数并初始化visited数组
    for(int i = 1; i <= n; i++) {
        visited[i] = 1;          // 初始化每个组的乘积为1
        cin >> data_[i];        // 读取第i个数
    }

    dfs(1, 1);    // 从第一个组和第一个数开始进行深度优先搜索
    cout << res << endl;    // 输出最终的最小分组数

    return 0;
}